{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Special Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSpecialNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计特殊整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果一个正整数每一个数位都是 <strong>互不相同</strong>&nbsp;的，我们称它是 <strong>特殊整数</strong> 。</p>\n",
    "\n",
    "<p>给你一个 <strong>正</strong>&nbsp;整数&nbsp;<code>n</code>&nbsp;，请你返回区间<em>&nbsp;</em><code>[1, n]</code>&nbsp;之间特殊整数的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 20\n",
    "<b>输出：</b>19\n",
    "<b>解释：</b>1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>1 到 5 所有整数都是特殊整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 135\n",
    "<b>输出：</b>110\n",
    "<b>解释：</b>从 1 到 135 总共有 110 个整数是特殊整数。\n",
    "不特殊的部分数字为：22 ，114 和 131 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-special-integers](https://leetcode.cn/problems/count-special-integers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-special-integers](https://leetcode.cn/problems/count-special-integers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['20', '5', '135']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        nlist = []\n",
    "        while n > 0:\n",
    "            nlist.append(n % 10)\n",
    "            n = n // 10\n",
    "\n",
    "        l = len(nlist)\n",
    "        zero_cnt = 0\n",
    "        for i in range(1, l):\n",
    "            zero_cnt += 9 * self.perm(9, i - 1)\n",
    "\n",
    "        res = zero_cnt\n",
    "        nset = set()\n",
    "        for i in range(l-1, -1, -1):\n",
    "            if nlist[i] >= 1:\n",
    "                start_n = 1 if (i == len(nlist) - 1) else 0\n",
    "                cnt = 0\n",
    "                for j in range(start_n, nlist[i]):\n",
    "                    if j not in nset:\n",
    "                        cnt += 1\n",
    "                if cnt > 0:\n",
    "                    res += cnt * self.perm(10 + i - l, i)\n",
    "\n",
    "            if nlist[i] in nset:\n",
    "                break\n",
    "            nset.add(nlist[i])\n",
    "\n",
    "        if len(nset) == l:\n",
    "            res += 1\n",
    "\n",
    "        return res\n",
    "    \n",
    "    def perm(self, m, n):\n",
    "        i = 0\n",
    "\n",
    "        res = 1\n",
    "        while i < n:\n",
    "            res *= m - i\n",
    "            i += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "meo = {}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.size = None\n",
    "        self.list = []\n",
    "\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        return self.solve(n)\n",
    "\n",
    "    def solve(self, n: int) -> int:\n",
    "        self.list.clear()\n",
    "        st = []\n",
    "        while n > 0:\n",
    "            st.append(n % 10)\n",
    "            n //= 10\n",
    "        self.size = len(st)\n",
    "        while st:\n",
    "            self.list.append(st.pop())\n",
    "        return self.dfs(0, 0, True, True)\n",
    "\n",
    "    def dfs(self, n: int, mark: int, limit: bool, zero: bool) -> int:\n",
    "        if n == self.size:\n",
    "            return int(not zero)\n",
    "\n",
    "        if not limit and not zero and (self.size - n, mark) in meo:\n",
    "            return meo[(self.size - n, mark)]\n",
    "\n",
    "        res = 0\n",
    "        up = self.list[n] if limit else 9\n",
    "        for i in range(up + 1):\n",
    "            if mark & (1 << i) == 0:\n",
    "                newMark = mark if zero and i == 0 else mark | (1 << i)\n",
    "                res += self.dfs(n + 1, newMark, limit and i == up, zero and i == 0)\n",
    "\n",
    "        if not limit and not zero:\n",
    "            meo[(self.size - n, mark)] = res\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "meo = {}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.size = None\n",
    "        self.list = []\n",
    "\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        return self.solve(n)\n",
    "\n",
    "    def solve(self, n: int) -> int:\n",
    "        self.list.clear()\n",
    "        st = []\n",
    "        while n > 0:\n",
    "            st.append(n % 10)\n",
    "            n //= 10\n",
    "        self.size = len(st)\n",
    "        while st:\n",
    "            self.list.append(st.pop())\n",
    "        return self.dfs(0, 0, True, True)\n",
    "\n",
    "    def dfs(self, n: int, mark: int, limit: bool, zero: bool) -> int:\n",
    "        if n == self.size:\n",
    "            return int(not zero)\n",
    "\n",
    "        if not limit and not zero and (self.size - n, mark) in meo:\n",
    "            return meo[(self.size - n, mark)]\n",
    "\n",
    "        res = 0\n",
    "        up = self.list[n] if limit else 9\n",
    "        for i in range(up + 1):\n",
    "            if mark & (1 << i) == 0:\n",
    "                newMark = mark if zero and i == 0 else mark | (1 << i)\n",
    "                res += self.dfs(n + 1, newMark, limit and i == up, zero and i == 0)\n",
    "\n",
    "        if not limit and not zero:\n",
    "            meo[(self.size - n, mark)] = res\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        l = len(s)\n",
    "        @cache\n",
    "        def dfs(pos,mask,islimit,iszero):\n",
    "            if pos == len(s):return 1 if mask else 0\n",
    "            if iszero:\n",
    "                if l-pos > 10:return 0\n",
    "                # print(l,pos,comb(10,l-pos)*factorial(l-pos) * 9 // 10)\n",
    "                return comb(10,l-pos)*factorial(l-pos) * 9 // 10 + dfs(pos+1,mask,False,True)\n",
    "            if not islimit:\n",
    "                res = 0\n",
    "                for i in range(10):\n",
    "                    if not mask >> i & 1:\n",
    "                        res += dfs(pos+1,mask | 1 << i,False,False)\n",
    "                return res\n",
    "            else:\n",
    "                res = 0\n",
    "                if int(s[pos]) > 0:\n",
    "                    if not mask:res += dfs(pos+1,mask,False,True)\n",
    "                    elif not mask & 1:res += dfs(pos+1,mask | 1,False,False)\n",
    "                    for i in range(1,int(s[pos])):\n",
    "                        if not mask >> i & 1:\n",
    "                            res += dfs(pos+1,mask | 1 << i,False,False)\n",
    "                if not mask >> int(s[pos]) & 1:\n",
    "                    res += dfs(pos+1,mask | 1 << int(s[pos]),True,False)\n",
    "            return res\n",
    "        res = dfs(0,0,True,False)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        ls=list(str(n))\n",
    "        k=len(ls)\n",
    "        def calx(l):\n",
    "            if l>9:\n",
    "                return 0\n",
    "            ret=1\n",
    "            i=0\n",
    "            la=9\n",
    "            while i<l:\n",
    "                ret*=la\n",
    "                if i!=0:\n",
    "                    la-=1\n",
    "                i+=1\n",
    "            return ret\n",
    "        @cache\n",
    "        def find(x,u,ss):\n",
    "            if x==k:\n",
    "                return 1\n",
    "            tp= int(ls[x]) if u else 9\n",
    "            tpp=0\n",
    "            for i in range(tp+1):\n",
    "                if x==0 and i==0:\n",
    "                    continue\n",
    "                if ss[i]=='1':\n",
    "                    continue\n",
    "                sss=list(ss)\n",
    "                sss[i]='1'\n",
    "                ss=\"\".join(sss)\n",
    "                #print(x+1,u and i==int(s[x]),ss)\n",
    "                tpp+=find(x+1,u and i==int(ls[x]),ss)\n",
    "                sss[i]='0'\n",
    "                ss=\"\".join(sss)\n",
    "            return tpp\n",
    "        ans=0\n",
    "        for i in range(k-1):\n",
    "            ans+=calx(i+1)\n",
    "        ans+=find(0,True,\"0000000000\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "meo = [[-1] * (1 << 10) for _ in range(10)]\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.size = None\n",
    "        self.list = []\n",
    "\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        return self.solve(n)\n",
    "\n",
    "    @cache\n",
    "    def solve(self, n: int) -> int:\n",
    "        self.list.clear()\n",
    "        st = []\n",
    "        while n > 0:\n",
    "            st.append(n % 10)\n",
    "            n //= 10\n",
    "        self.size = len(st)\n",
    "        while st:\n",
    "            self.list.append(st.pop())\n",
    "        return self.dfs(0, 0, True, True)\n",
    "\n",
    "    @cache\n",
    "    def dfs(self, n: int, mark: int, limit: bool, zero: bool) -> int:\n",
    "        if n == self.size:\n",
    "            return int(not zero)\n",
    "\n",
    "        if not limit and not zero and meo[self.size - n][mark] != -1:\n",
    "            return meo[self.size - n][mark]\n",
    "\n",
    "        res = 0\n",
    "        up = self.list[n] if limit else 9\n",
    "        for i in range(up + 1):\n",
    "            if mark & (1 << i) == 0:\n",
    "                newMark = mark if zero and i == 0 else mark | (1 << i)\n",
    "                res += self.dfs(n + 1, newMark, limit and i == up, zero and i == 0)\n",
    "\n",
    "        if not limit and not zero:\n",
    "            meo[self.size - n][mark] = res\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        ls=len(s)\n",
    "        dp=[[-1]*1024 for _ in range(ls)]\n",
    "        def f(i,mask,is_lim,is_num):\n",
    "            if i==ls:return int(is_num)\n",
    "            res=0\n",
    "            if not is_num:\n",
    "                res=f(i+1, mask, False, False)\n",
    "            if not is_lim and dp[i][mask]>=0:return dp[i][mask]\n",
    "            up=int(s[i]) if is_lim else 9\n",
    "            for d in range(1-int(is_num),up+1):\n",
    "                if mask>>d & 1==0:\n",
    "                    res+=f(i+1, mask|(1<<d),is_lim and up==d, True)\n",
    "            if not is_lim and is_num:dp[i][mask]=res\n",
    "            return res\n",
    "        return f(0,0,True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        a = []\n",
    "        while n:\n",
    "            a.append(n%10)\n",
    "            n //=10\n",
    "        dp = [[-1 for _ in range(1 << 10)] for _ in range(len(a))] \n",
    "        #  dp[pos][status] 定义当前位置pos时，已经加入集合的正整数状态为state的合法特殊整数数目。\n",
    "        \n",
    "        def dfs(pos, status, limit): # 通过state判断前导0是否存在，不需要额外lead变量\n",
    "            if pos < 0:\n",
    "                return 1\n",
    "            if not limit and dp[pos][status] != -1:\n",
    "                return dp[pos][status]\n",
    "            ans = 0\n",
    "            up = a[pos] if limit else 9\n",
    "            for i in range(0, up+1):\n",
    "                if pos == 0 and status == 0 and i == 0: continue # 去除掉不符合的0\n",
    "                elif status == 0 and i == 0:  # 对于前导0的情况另外处理，0不加入集合中。\n",
    "                    ans += dfs(pos-1, status, limit and a[pos]==i,)  \n",
    "                elif status >> i & 1 == 0:\n",
    "                    ans += dfs(pos-1, status|(1<<i), limit and a[pos]==i)    \n",
    "            if not limit:\n",
    "                dp[pos][status] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dfs(len(a)-1, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        def traversal(depth, mask, isNum, isLimit):\n",
    "            nonlocal s\n",
    "            nonlocal table\n",
    "            if depth == len(s):\n",
    "                return isNum\n",
    "            if (isNum and not isLimit and table[depth][mask] != -1):\n",
    "                return table[depth][mask]\n",
    "            res = 0 if isNum else traversal(depth + 1, mask, False, False)\n",
    "            up = int(s[depth]) if isLimit else 9\n",
    "            low = 0 if isNum else 1\n",
    "            for i in range(low, up + 1):\n",
    "                if (mask >> i & 1 == 0):\n",
    "                    res += traversal(depth + 1, mask | (1 << i), True, isLimit and i == up)\n",
    "            if (not isLimit and isNum):\n",
    "                table[depth][mask] = res\n",
    "            return res\n",
    "        s = str(n)\n",
    "        table = [[-1] * 1024 for _ in range(len(s))]\n",
    "        return traversal(0, 0, False, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "\n",
    "        nArray = str(n)\n",
    "        meo = [[0]*(1<<10) for _ in range(len(nArray))]\n",
    "        def calNum(tempBit,isLimit,mask,hasNum):\n",
    "            if tempBit == len(nArray):\n",
    "                return hasNum\n",
    "            if not isLimit and meo[tempBit][mask] != 0:\n",
    "                return meo[tempBit][mask]\n",
    "            up = ord(nArray[tempBit])-ord('0') if isLimit else 9\n",
    "            res = 0\n",
    "            if not hasNum:\n",
    "                res += calNum(tempBit+1, False, mask, hasNum)\n",
    "            # if hasNum and (mask & 1) == 0:\n",
    "            #     res += calNum(tempBit+1, isLimit&(up==0), mask|1, hasNum)\n",
    "            for digit in range(1 if not hasNum else 0,up+1):\n",
    "                if (mask & (1 << digit)) == 0:\n",
    "                    temp_mask = (1 << digit) | mask\n",
    "                    res += calNum(tempBit+1, isLimit&(digit==up), temp_mask, True)\n",
    "            if not isLimit:\n",
    "                meo[tempBit][mask] = res\n",
    "            return res\n",
    "\n",
    "\n",
    "        return calNum(0, True, 0, False)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        @params\n",
    "        pos - 第几位\n",
    "        mask - 之前用了哪些数\n",
    "        is_limit - 之前的几位是顶吗?\n",
    "        \"\"\"\n",
    "        n = str(n)\n",
    "        k = len(n)\n",
    "        states = 1 << 10\n",
    "        dp = [[-1] * states for _ in range(k)]\n",
    "\n",
    "        def dfs(pos, mask, is_limit):\n",
    "            if pos == k:\n",
    "                return 1\n",
    "            if (not is_limit) and dp[pos][mask] != -1:\n",
    "                return dp[pos][mask]\n",
    "            up = 9 if not is_limit else int(n[pos])\n",
    "            lo = 1 if not mask else 0 \n",
    "            ans = 0\n",
    "            if not mask: # 前导0,可以跳过当前位\n",
    "                ans += dfs(pos + 1, mask, False)\n",
    "            for i in range(lo, up + 1): # 如果前面都是0,则当前位不能从0开始, if not mask已经cover当前位是0的case\n",
    "                if not (mask & (1 << i)):\n",
    "                    ans += dfs(pos + 1, mask | (1 << i), is_limit and i == int(n[pos]))\n",
    "            if not is_limit:\n",
    "                dp[pos][mask] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, 0, True) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        @params\n",
    "        pos - 第几位\n",
    "        mask - 之前用了哪些数\n",
    "        is_limit - 之前的几位是顶吗?\n",
    "        \"\"\"\n",
    "        n = str(n)\n",
    "        k = len(n)\n",
    "        states = (1 << 10) - 1\n",
    "        dp = [[-1] * states for _ in range(k)]\n",
    "\n",
    "        def dfs(pos, mask, is_limit):\n",
    "            if pos == k:\n",
    "                return 1\n",
    "            if (not is_limit) and dp[pos][mask] != -1:\n",
    "                return dp[pos][mask]\n",
    "            up = 9 if not is_limit else int(n[pos])\n",
    "            lo = 1 if not mask else 0 \n",
    "            ans = 0\n",
    "            if not mask: # 前导0,可以跳过当前位\n",
    "                ans += dfs(pos + 1, mask, False)\n",
    "            for i in range(lo, up + 1): # 如果前面都是0,则当前位不能从0开始, if not mask已经cover当前位是0的case\n",
    "                if not (mask & (1 << i)):\n",
    "                    ans += dfs(pos + 1, mask | (1 << i), is_limit and i == int(n[pos]))\n",
    "            if not is_limit:\n",
    "                dp[pos][mask] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, 0, True) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        def count(cur_bit, used, on_bound, can_use_zero):\n",
    "            if cur_bit == n:\n",
    "                return 1 if can_use_zero else 0\n",
    "\n",
    "            state = (cur_bit, used, on_bound, can_use_zero)\n",
    "            if state not in memory:\n",
    "                res = 0 if can_use_zero else count(cur_bit + 1, used, False, False)\n",
    "                flag = 1\n",
    "                max_can_use = 9 if not on_bound else int(num[cur_bit])\n",
    "                for digit in range(max_can_use + 1):\n",
    "                    if used & flag:\n",
    "                        flag <<= 1\n",
    "                        continue\n",
    "                    if digit == 0 and not can_use_zero:\n",
    "                        flag <<= 1\n",
    "                        continue\n",
    "                    res += count(cur_bit + 1, used | flag, on_bound & (digit == max_can_use), True)\n",
    "                    flag <<= 1\n",
    "                memory[state] = res\n",
    "            return memory[state]\n",
    "\n",
    "        num = str(n)\n",
    "        n = len(num)\n",
    "        memory = {}\n",
    "        return count(0, 0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        dp = [[-1] * 1024 for _ in range(12)]\n",
    "        \n",
    "        def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:\n",
    "            if not is_limit and is_num and dp[i][mask] != -1:\n",
    "                return dp[i][mask]\n",
    "            if i == len(s):\n",
    "                return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "            res = 0\n",
    "            if not is_num:  # 可以跳过当前数位\n",
    "                res = f(i + 1, mask, False, False)\n",
    "            low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "            up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                if (mask >> d & 1) == 0:  # d 不在 mask 中\n",
    "                    res += f(i + 1, mask | (1 << d), is_limit and d == up, True)\n",
    "            if not is_limit and is_num and dp[i][mask] == -1:\n",
    "                dp[i][mask] = res\n",
    "            return res\n",
    "        return f(0, 0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        # is_limit 表示\n",
    "        memo = {} # 记忆化搜索\n",
    "        def f(i, mask, is_limit, is_num):\n",
    "            if (i, mask, is_limit, is_num) in memo:\n",
    "                return memo[(i, mask, is_limit, is_num)]\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += f(i+1, mask, False, False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(1-int(is_num), up+1):\n",
    "                if mask >> d & 1 == 0:\n",
    "                    res += f(i+1, mask|(1 << d), is_limit and d == up, True)\n",
    "            memo[(i, mask, is_limit, is_num)] = res\n",
    "            return res\n",
    "        return f(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int, is_num: bool, is_limit: bool) -> bool:\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            ans = 0\n",
    "            if not is_num:\n",
    "                ans += dfs(i + 1, mask, False, False)\n",
    "            down = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for num in range(down, up + 1):\n",
    "                if ((mask >> num) & 1) == 0:\n",
    "                    ans += dfs(i + 1, mask | (1 << num), True, is_limit and (num == up))\n",
    "            return ans \n",
    "        return dfs(0, 0, False, True)\n",
    "        # s = str(n)\n",
    "        # @cache  # 记忆化搜索\n",
    "        # def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:\n",
    "        #     if i == len(s):\n",
    "        #         return int(is_num)  # is_num 为 True 表示得到了一个合法数字\n",
    "        #     res = 0\n",
    "        #     if not is_num:  # 可以跳过当前数位\n",
    "        #         res = f(i + 1, mask, False, False)\n",
    "        #     low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "        #     up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "        #     for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "        #         if (mask >> d & 1) == 0:  # d 不在 mask 中\n",
    "        #             res += f(i + 1, mask | (1 << d), is_limit and d == up, True)\n",
    "        #     return res\n",
    "        # return f(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, mask, equal):\n",
    "            if i == len(s): return int(mask != 0)\n",
    "            ans = 0\n",
    "            for j in range(10):\n",
    "                if j == 0 and mask == 0:\n",
    "                    ans += dfs(i + 1, mask, False)\n",
    "                elif equal and str(j) > s[i]:\n",
    "                    break\n",
    "                elif 1 & (mask >> j) == 0:\n",
    "                    ans += dfs(i + 1, mask | (1 << j), equal and str(j) == s[i])\n",
    "            return ans\n",
    "        return dfs(0, 0, True)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        #返回所有数位都不同的数字的个数，mask表示已选数字的掩码\n",
    "        @cache\n",
    "        def f(indx, limit, mask):\n",
    "            if indx == -1:\n",
    "                return 1 if mask > 0 else 0\n",
    "            res, k = 0, n//(10**indx)%10 #第indx位的数字\n",
    "            for i in range(k+1 if limit else 10):\n",
    "                if (1<<i)&mask > 0:\n",
    "                    continue\n",
    "                res += f(indx - 1, limit and i == k,mask if i==0 and mask == 0 else mask|(1<<i) )\n",
    "            return res\n",
    "        return f(len(str(n))-1, True, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "    \n",
    "        @cache # 记忆化搜索\n",
    "        def f(i,mask,is_limit,is_number):\n",
    "            if i==len(s):\n",
    "                return int(is_number) # is_num 为 True 表示得到了一个合法数字\n",
    "            res = 0\n",
    "            if not is_number:  # 可以跳过当前数位\n",
    "                res = f(i+1,mask,False,False)\n",
    "            up = int(s[i]) if is_limit else 9 # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in range(1-int(is_number),up+1):  # 枚举要填入的数字 d\n",
    "                if mask >> d & 1 ==0:  # d 不在 mask 中\n",
    "                    res+= f(i+1,mask|(1<<d),is_limit and d == up,True)\n",
    "            return res\n",
    "        return f(0,0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        @cache\n",
    "        def f(i, mask, is_limit, is_num):\n",
    "            if i == len(n):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += f(i + 1, mask, False, False)\n",
    "            up = int(n[i]) if is_limit else 9\n",
    "            down = 0 if is_num else 1\n",
    "            for num in range(down, up + 1):\n",
    "                if (mask >> num) & 1:\n",
    "                    res += f(i + 1, mask ^ (1 << num), is_limit and num == up, True)\n",
    "            return res\n",
    "        return f(0, (1 << 10) - 1, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        m=len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,mask,is_limit,is_num):\n",
    "            if i==m:\n",
    "                return bool(is_num)\n",
    "            res=0\n",
    "            if not is_num:\n",
    "                res+=dfs(i+1,mask,False,False)\n",
    "            minv=0 if is_num else 1\n",
    "            maxv=int(s[i]) if is_limit else 9\n",
    "            for d in range(minv,maxv+1):\n",
    "                if (mask>>d) & 1==0:\n",
    "                    res+=dfs(i+1,mask|(1<<d),is_limit and d==maxv,True)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        m=len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,mask,is_limit,is_num):\n",
    "            if i==m:\n",
    "                return is_num\n",
    "            res=0\n",
    "            if not is_num:\n",
    "                res+=dfs(i+1,mask,False,False)\n",
    "            minv=0 if is_num else 1\n",
    "            maxv=int(s[i]) if is_limit else 9\n",
    "            for d in range(minv,maxv+1):\n",
    "                if (mask>>d) & 1==0:\n",
    "                    res+=dfs(i+1,mask|(1<<d),is_limit and d==maxv,True)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, mask: int, isLimit: bool, isNum: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(isNum)\n",
    "            ans = 0\n",
    "            if not isNum:\n",
    "                ans = f(i + 1, mask, False, False) # 直接跳过 （数值大小与前导0一样，但是体现为为添加过数字，isNum为False,并且无limit\n",
    "            low = 0 if isNum else 1\n",
    "            up = int(s[i]) if isLimit else 9\n",
    "            for d in range(low, up + 1):\n",
    "                if not (mask >> d) & 1:\n",
    "                    ans += f(i + 1, mask | (1 << d), isLimit and d == up, isNum=True)  # 添加过数字 符合无前导0的条件\n",
    "            return ans\n",
    "\n",
    "        return f(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        @lru_cache(maxsize=204800)\n",
    "        def f(i, mask, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            ans = 0\n",
    "            if not is_num:\n",
    "                ans = f(i+1, mask, False, False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(1-int(is_num), up+1):\n",
    "                if mask >> d & 1 == 0:\n",
    "                    ans += f(i + 1, mask | (1 << d), is_limit and d == up, True)\n",
    "            return ans\n",
    "        s = str(n)\n",
    "        return f(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        @cache\n",
    "        def search(i, used, is_limit, is_num):\n",
    "            if i == len(n):\n",
    "                return is_num\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += search(i+1, used, False, is_num)\n",
    "            used_list = list(used)\n",
    "            up = int(n[i]) if is_limit else 9\n",
    "            low = 0 if is_num else 1\n",
    "            for j in range(low, up+1):\n",
    "                if used[j] == '1':\n",
    "                    continue\n",
    "                used_list[j] = '1'\n",
    "                res += search(i+1, \"\".join(used_list), is_limit and j==up, True)\n",
    "                used_list[j] = '0'\n",
    "            # print(i, used, is_limit, is_num, res)\n",
    "            return res\n",
    "\n",
    "        return search(0, '0'*10, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "\n",
    "        arr = []\n",
    "        v = n\n",
    "        while v:\n",
    "            arr.append(v % 10)\n",
    "            v //= 10\n",
    "\n",
    "        arr = arr[::-1]\n",
    "        n = len(arr)\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(stat, all_zero, all_max, ii) -> int:\n",
    "            if ii == n:\n",
    "                return 1 if not all_zero else 0\n",
    "\n",
    "            bound = arr[ii] if all_max else 9\n",
    "            ans = 0\n",
    "            for val in range(0, bound+1):\n",
    "                if stat & (1 << val):\n",
    "                    continue\n",
    "\n",
    "                ns = stat\n",
    "                if not (val == 0 and all_zero):\n",
    "                    ns |= (1 << val)\n",
    "\n",
    "                ans += dp(ns, all_zero and val == 0, all_max and val == bound, ii+1)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dp(0, True, True, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        if n <= 10:\n",
    "            return n\n",
    "        # f: 标记已经使用过的数\n",
    "        # k: 要组合的数长度\n",
    "        # t: 组合的数大小要小于等于t\n",
    "        @cache\n",
    "        def dfs(f:int,k:int,t)->int:\n",
    "            # t为负数不可能构成小于等于t的数直接返回0\n",
    "            if t < 0:\n",
    "                return 0\n",
    "            # 遍历到头了找到了一种可行方案返回1\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            r = 0\n",
    "            for i in range(10):\n",
    "                # 不是特殊数字 continue\n",
    "                if (f >> i) & 1:\n",
    "                    continue\n",
    "                # 长度为k的数首位数字\n",
    "                p = i\n",
    "                m = int(pow(10,k-1))\n",
    "                a = t // m\n",
    "                b = t % m\n",
    "                # 以p开头的长度为k的数一定小于以a为前缀，后缀长度为k-1的数\n",
    "                if p < a:\n",
    "                    # 这里输入m-1实际上是保证后续找到的数 <= 999...\n",
    "                    r += dfs(f | (1 << i), k-1,m-1)\n",
    "                elif p == a:\n",
    "                    # b为取模之后的\n",
    "                    r += dfs(f | (1 << i), k-1,b)\n",
    "                else:\n",
    "                    break\n",
    "            return r\n",
    "        res = 0\n",
    "        for i in range(1,12):\n",
    "            # 计算过程中并未对0开头的数进行特殊处理，这里需要减去以0开头长度为i-1的符合要求的数\n",
    "            res += dfs(0,i,n) - dfs(1,i-1,n)\n",
    "        return res\n",
    "\n",
    "s = Solution()\n",
    "s.countSpecialNumbers(135)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,all_zero,all_max,state):\n",
    "            if i == target:return 1 if not all_zero else 0\n",
    "            max_num = 10 if not all_max else int(num[i]) + 1\n",
    "            ans = 0\n",
    "            for cur in range(max_num):\n",
    "                if all_zero or not state[cur]:\n",
    "                    if all_zero and cur == 0:\n",
    "                        ans += dfs(i + 1 , all_zero and cur == 0 ,all_max and cur == int(num[i]),state)\n",
    "                        continue\n",
    "                    new_state = list(state)\n",
    "                    new_state[cur] = True\n",
    "                    ans += dfs(i + 1 , all_zero and cur == 0 ,all_max and cur == int(num[i]),tuple(new_state))\n",
    "            return ans\n",
    "\n",
    "        num = str(n)\n",
    "        target = len(num)\n",
    "        return dfs(0,True,True,tuple([False for i in range(10)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def countSpecialNumbers(self, n: int) -> int:\n",
    "    #     n = str(n)\n",
    "    #     mdict = {}\n",
    "    #     def f(i, used, isLimit, isNum):\n",
    "    #         key = str(i)+str(used)+str(int(isLimit))+str(int(isNum))\n",
    "    #         if key in mdict:\n",
    "    #             return mdict[key]\n",
    "    #         if i == len(n):\n",
    "    #             if not isNum:\n",
    "    #                 return 0\n",
    "    #             return 1\n",
    "    #         rst = 0\n",
    "    #         minV = 0\n",
    "    #         if not isNum:\n",
    "    #             rst += f(i+1, used, False, False)\n",
    "    #             minV = 1\n",
    "    #         maxV = 9\n",
    "    #         if isLimit:\n",
    "    #             maxV = int(n[i])\n",
    "    #         for v in range(minV, maxV+1):\n",
    "    #             if (used >> v) & 1 == 0:\n",
    "    #                 rst += f(i+1, (1 << v) | used, v==maxV and isLimit, True)\n",
    "    #         mdict[key] = rst\n",
    "    #         return rst\n",
    "    #     return f(0, 0, True, False)\n",
    "\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        mdict = {}\n",
    "        def f(i, used, isLimit, isNum):\n",
    "            used.sort()\n",
    "            key = str(i)+str(used)+str(int(isLimit))+str(int(isNum))\n",
    "            if key in mdict:\n",
    "                return mdict[key]\n",
    "            if i == len(n):\n",
    "                if not isNum:\n",
    "                    return 0\n",
    "                return 1\n",
    "            rst = 0\n",
    "            minV = 0\n",
    "            if not isNum:\n",
    "                rst += f(i+1, used, False, False)\n",
    "                minV = 1\n",
    "            maxV = 9\n",
    "            if isLimit:\n",
    "                maxV = int(n[i])\n",
    "            for v in range(minV, maxV+1):\n",
    "                if v not in used:\n",
    "                    rst += f(i+1, used+[v], v==maxV and isLimit, True)\n",
    "            mdict[key] = rst\n",
    "            return rst\n",
    "        return f(0, [], True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        mark = [True] * 10\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, limit, is_num, mark):\n",
    "            if i == len(s):\n",
    "                return is_num\n",
    "            cnt = 0\n",
    "            if not is_num:\n",
    "                cnt += dfs(i+1, False, False, mark)\n",
    "            up = int(s[i]) if limit else 9\n",
    "            start = 0 if is_num else 1\n",
    "            mark = list(mark)\n",
    "            for d in range(start, up+1):\n",
    "                if mark[d]:\n",
    "                    mark[d] = False\n",
    "                    cnt += dfs(i+1, limit and up==d, True, tuple(mark))\n",
    "                    mark[d] = True\n",
    "            return cnt\n",
    "        return dfs(0, True, False, tuple(mark))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        # Fill in your code for the function. Do not change the function name\n",
    "        # The function should return an integer.\n",
    "        n_str = str(n)\n",
    "        n_len = len(n_str)\n",
    "        n_unique = 0\n",
    "\n",
    "\n",
    "        # get the all the x000 unique digits\n",
    "        if n > 10:\n",
    "            for i in range(n_len-1):\n",
    "                n_unique = n_unique + 9*int(np.math.factorial(9)/np.math.factorial(10-n_len+i+1))\n",
    "            m=0\n",
    "            if m == 0:\n",
    "                n_first  = (int(n_str[m])-1)*int(np.math.factorial(9)/np.math.factorial(10-n_len))\n",
    "            m=m+1\n",
    "            count_last=0\n",
    "            n_sec=0\n",
    "\n",
    "\n",
    "            for k in range(n_len-1):\n",
    "                if m == n_len-1:\n",
    "                    count_last = int(n_str[m])+1\n",
    "                    for l in range(int(n_str[m])+1):\n",
    "                        if n_str[0:n_len-1].count(str(l)) > 0:\n",
    "                            count_last = count_last-1\n",
    "\n",
    "                else:\n",
    "                    for s in range(int(n_str[k+1])):\n",
    "                        if n_str[0:k+1].count(str(s))>0:\n",
    "                            n_sec=n_sec\n",
    "                        else:\n",
    "                            n_sec = int(np.math.factorial(9-m)/np.math.factorial(10-n_len))+n_sec\n",
    "                    if n_str[0:k+1].count(n_str[k+1]) > 0:\n",
    "                        break\n",
    "                    m= m+1\n",
    "\n",
    "            value=n-(n_sec+n_first+n_unique+count_last)\n",
    "        else:\n",
    "            value = 0\n",
    "        return n - value\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        a = [str(j) for j in range( 10)]\n",
    "        n = len(s) \n",
    "        @cache \n",
    "        def f(j, pre, havPre, limit):\n",
    "            if j==n:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            pre = set(pre)\n",
    "            b = {j for j in a if j not in pre}\n",
    "            if havPre==0:\n",
    "                ans+=f(j+1, tuple([]), 0, 0) \n",
    "                b.remove('0')\n",
    "            c = s[j] if limit else '9'\n",
    "            for k in b:\n",
    "                    if k<=c:                   \n",
    "                        tmp = tuple([k] + list(pre))\n",
    "                        ans+=f(j+1, tmp, 1, limit&(k==c))\n",
    "            return ans \n",
    "        return f(0, tuple([]), 0, 1)-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        a = []\n",
    "        while n:\n",
    "            a.append(n % 10)\n",
    "            n //= 10\n",
    "        p = len(a)\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos, lead, lim: bool, status) -> int:\n",
    "            if pos == -1:\n",
    "                return 1\n",
    "            ret = 0\n",
    "            up = a[pos] if lim else 9\n",
    "            for i in range(up + 1):\n",
    "                if (status >> i) & 1:\n",
    "                    continue\n",
    "                to_status = status | (1 << i) if any((i, lead)) else status\n",
    "                ret += dfs(pos - 1, i > 0, lim and (i == a[pos]), to_status)\n",
    "            return ret\n",
    "        return dfs(p - 1, 0, 1, 1 << 10) - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        m = len(s)\n",
    "\n",
    "        @cache\n",
    "        def dp(i: int, mask: bool,repeat: bool, limit: bool, isNum: bool) -> int:\n",
    "            if i == m: return isNum and not repeat\n",
    "            res = 0\n",
    "            if not isNum:\n",
    "                res += dp(i+1, mask, False, False, False)\n",
    "            up = int(s[i]) if limit else 9\n",
    "            for d in range(1-isNum, up+1):\n",
    "                if (mask>>d)&1 != 0:\n",
    "                    res += dp(i+1, mask, True, limit and up==d, True)\n",
    "                else:\n",
    "                    res += dp(i+1, mask|(1<<d), repeat, limit and up==d, True)\n",
    "            return res\n",
    "        \n",
    "        return dp(0, 0, False, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        # num = list(map(int, str(n + 1)))\n",
    "        # st = set()\n",
    "        # m = len(num)\n",
    "        # res = sum(9 * perm(9, i) for i in range(m - 1))\n",
    "        # for i, x in enumerate(num) :\n",
    "        #     for j in range(i == 0, x) :\n",
    "        #         if j not in st :\n",
    "        #             res += perm(9 - i, m - i - 1)\n",
    "        #     if x in st :\n",
    "        #         break\n",
    "        #     st.add(x)\n",
    "        # return res\n",
    "        \n",
    "        num = list(map(int, str(n)))\n",
    "        m = len(num)\n",
    "\n",
    "        @cache\n",
    "        def f(i, mask, islimit, isnum) :\n",
    "            if i >= m :\n",
    "                if isnum :\n",
    "                    return 1\n",
    "                else :\n",
    "                    return 0\n",
    "            res = 0\n",
    "            limit = num[i] if islimit else 9\n",
    "            for j in range(limit + 1) :\n",
    "                if j == limit :\n",
    "                    islimit1 = islimit\n",
    "                else :\n",
    "                    islimit1 = False\n",
    "                if mask == 0 and j == 0 :\n",
    "                    mask1 = 0\n",
    "                else :\n",
    "                    mask1 = mask | (1 << j)\n",
    "                if mask & (1 << j) :\n",
    "                    isnum1 = True\n",
    "                else :\n",
    "                    isnum1 = isnum\n",
    "                res += f(i + 1, mask1, islimit1, isnum1)\n",
    "            return res\n",
    "        \n",
    "        return n - f(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        nums = [int(x) for x in str(n)]\n",
    "        @cache\n",
    "        def dfs(pre, wei, repeat, limit):#前导集合，位，是否满足要求，前导限制\n",
    "            if repeat:\n",
    "                if not limit:\n",
    "                    return 10 ** (len(nums)-wei)\n",
    "            if wei == len(nums):\n",
    "                return int(repeat)\n",
    "            res = 0\n",
    "            p = nums[wei] if limit else 10\n",
    "            if p == 0:\n",
    "                res += dfs(pre|1,wei+1,(pre&1)>0 or repeat,True)\n",
    "            else:\n",
    "                if not pre:\n",
    "                    res += dfs(0,wei+1,repeat,False)\n",
    "                else:\n",
    "                    res += dfs(pre|1,wei+1,(pre&1) or repeat,False)\n",
    "                for i in range(1,p):\n",
    "                    res += dfs(pre|(1<<i),wei+1,(pre&(1<<i))>0 or repeat,False)\n",
    "                if limit:\n",
    "                    res += dfs(pre|(1<<p),wei+1,(pre&(1<<p))>0 or repeat,True)\n",
    "            return res\n",
    "        return n - dfs(0, 0, False, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import perm\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        if n<10:\n",
    "            return n\n",
    "        ret = 0\n",
    "        num_digits = len(str(n))\n",
    "        \n",
    "        dp = [0]*(num_digits+1)\n",
    "        for i in range(1, num_digits):\n",
    "            dp[i] = 9*int(perm(9, i-1))\n",
    "        print(dp)\n",
    "        seen = set([])\n",
    "        for i in range(num_digits):\n",
    "            cur_max = int(str(n)[i])\n",
    "            if cur_max in seen:\n",
    "                all_avail = set([i for i in range(cur_max)])\n",
    "                avail_num = len(all_avail - seen)\n",
    "                p = avail_num*int(perm(9-i, num_digits-i-1))\n",
    "                dp[-1] += p\n",
    "                break\n",
    "            print(i, cur_max, int(perm(9-i, num_digits-i-1)))\n",
    "            seen.add(cur_max)\n",
    "            if cur_max==0:\n",
    "                p = 0\n",
    "            else:\n",
    "                if i==0:\n",
    "                    p = (cur_max-1)*int(perm(9-i, num_digits-i-1))\n",
    "                else:\n",
    "                    all_avail = set([i for i in range(cur_max)])\n",
    "                    avail_num = len(all_avail - seen)\n",
    "                    p = avail_num*int(perm(9-i, num_digits-i-1))\n",
    "            dp[-1] += p\n",
    "            print(p)\n",
    "        print(dp)\n",
    "        plus = int(len(set([c for c in str(n)]))==len(str(n)))\n",
    "        print(plus, set([c for c in str(n)]))\n",
    "        return sum(dp)+plus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        @cache\n",
    "        def dfs(i,is_limit,is_num,tmp,flag):  \n",
    "            if i==len(s):\n",
    "                return int(flag)\n",
    "            res=0\n",
    "            if not is_num:\n",
    "                res=dfs(i+1,False,False,0,False) \n",
    "            l=0 if is_num else 1\n",
    "            r=int(s[i]) if is_limit else 9\n",
    "            for d in range(l,r+1):\n",
    "                if tmp>>d&1:\n",
    "                    res+=dfs(i+1,is_limit and d==r,True,tmp,True)\n",
    "                else:\n",
    "                    res+=dfs(i+1,is_limit and d==r,True,tmp|(1<<d),flag)\n",
    "            return res\n",
    "        return (n)-dfs(0,True,False,0,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "from typing import List\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def countSpecialNumbers(self, n: int) -> int:\r\n",
    "        # Digit DP\r\n",
    "        # Digit DP Template: https://www.bilibili.com/video/BV1rS4y1s721/\r\n",
    "        # Similar to 902. Numbers At Most N Given Digit Set\r\n",
    "        # 所問的數字是 0~n 中的特殊數字，即每個digit都是0~9中的一個，且沒有重複的digit\r\n",
    "\r\n",
    "        s = str(n)\r\n",
    "\r\n",
    "        # cal(i, mask, is_limit, is_num) 表示当前已经填了前 i 位，当前的数字为 mask，之前的数字是否和 n 相等为 is_limit，之前是否已经填了一个合法数字为 is_num\r\n",
    "        # mask 為二進位表示的集合，例如集合 {0,2,3} 對應的二進位表示為 1101，即 mask = 13\r\n",
    "        #   如果 d 在 mask 中，則 mask >> d & 1 == 1\r\n",
    "        #   把 d 加入 mask 中，則 mask = mask | (1 << d)\r\n",
    "        # is_limit 表示之前的digit都和n一樣，所以這一位最大只能填s[i]\r\n",
    "        # is_num 表示之前已經填了一個合法數字，因為不能有前導0，如果為False，則可以跳過當前digit或從1開始填，如果為True，則可以從0開始填\r\n",
    "\r\n",
    "        # @cache # memoize\r\n",
    "        # def cal(i: int, mask: int, is_limit: bool, is_num: bool) -> int:\r\n",
    "        #     if i == len(s): # 填完所有位數，若此數字合法(is_num)，則返回1，否則返回0\r\n",
    "        #         return int(is_num)\r\n",
    "        #     res = 0 # 當前位數下，符合條件的特殊數字數量，初始為0\r\n",
    "        #     if not is_num:  # 當還沒填合法數字時，可跳過當前digit\r\n",
    "        #         res = cal(i + 1, mask, False, False)\r\n",
    "        #     lower = 0 if is_num else 1  # is_num\r\n",
    "        #     upper = int(s[i]) if is_limit else 9  # is_limit\r\n",
    "        #     for d in range(lower, upper + 1):  # 遍歷當前digit\r\n",
    "        #         if (mask >> d & 1) == 0:  # 若 d 不在 mask 中，即 d 沒有填過\r\n",
    "        #             res += cal(i + 1, mask | (1 << d), is_limit and d == upper, True) # 將此位填入 d，並更新 mask\r\n",
    "        #     return res\r\n",
    "        # return cal(0, 0, True, False)\r\n",
    "\r\n",
    "        @cache # memoize\r\n",
    "        def cal(i: int, mask: List[int], is_limit: bool, is_num: bool) -> int:\r\n",
    "            if i == len(s): # 填完所有位數，若此數字合法(is_num)，則返回1，否則返回0\r\n",
    "                return int(is_num)\r\n",
    "            res = 0 # 當前位數下，符合條件的特殊數字數量，初始為0\r\n",
    "            if not is_num:  # 當還沒填合法數字時，可跳過當前digit\r\n",
    "                res = cal(i + 1, frozenset(mask), False, False)\r\n",
    "            lower = 0 if is_num else 1  # is_num\r\n",
    "            upper = int(s[i]) if is_limit else 9  # is_limit\r\n",
    "            for d in range(lower, upper + 1):  # 遍歷當前digit\r\n",
    "                if d not in mask: # 若 d 不在 mask 中，即 d 沒有填過\r\n",
    "                    res += cal(i + 1, frozenset(list(mask) + [d]), is_limit and d == upper, True) # 將此位填入 d，並更新 mask\r\n",
    "            return res\r\n",
    "        return cal(0, frozenset([]), True, False)\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
